package com.zj.leetcode.medium.greed;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @program: algorithm
 * @description: 分割数组为连续子序列
 * 659 split-array-into-consecutive-subsequences
 * @author: Zhang Bo
 * @create: 2022-04-12 11:03:51
 **/
public class SplitArrayIntoConsecutiveSubsequences {
    public static void main(String[] args) {
//        int[] nums = {1,2,3,3,4,4,5,5,6,7,8,8,9,9,10,10};
        int[] nums = {1,2,3,3,4,5};
        Solution solution = new SplitArrayIntoConsecutiveSubsequences().new Solution();
        System.out.println(solution.isPossible(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public boolean isPossible(int[] nums) {
            HashMap<Integer, Integer> freq = new HashMap<>();
            HashMap<Integer, Integer> need = new HashMap<>();
            ArrayList<ArrayList<Integer>> list = new ArrayList<>();
            for(int num: nums){
                freq.put(num, freq.getOrDefault(num, 0)+1);
            }
            for(int i=0; i<nums.length; i++){
                if(freq.get(nums[i]) == 0){
                    continue;
                }
                // 可以加在后面
                else if(need.containsKey(nums[i]) && need.get(nums[i]) > 0){
                    freq.put(nums[i], freq.get(nums[i])-1);
                    need.put(nums[i], need.get(nums[i])-1);
                    need.put(nums[i]+1, need.getOrDefault(nums[i]+1, 0)+1);
                }
                // 不能加在后面
                else if(freq.get(nums[i])>0 && freq.getOrDefault(nums[i]+1, 0)>0 && freq.getOrDefault(nums[i]+2, 0)>0){
                    freq.put(nums[i], freq.get(nums[i])-1);
                    freq.put(nums[i]+1, freq.get(nums[i]+1)-1);
                    freq.put(nums[i]+2, freq.get(nums[i]+2)-1);
                    need.put(nums[i]+3, need.getOrDefault(nums[i]+3, 0)+1);
                }else{
                    return false;
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}